package com.tsx.leetcode.hot100.easy;

/**
 * Q160 相交链表
 * <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists">相交链表</a>
 * 由于两条链表的右端是对齐的 所以公共部分的长度是一样的
 * 假设A链表非公共部分为a长度，B链表非公共部分为b长度
 * 两个链表的公共长度为c
 * a+c+b = b+c+a
 * 解题方法：
 * 1. 当某一链表的游标为空的时候，游标为另一链表起点
 * 2. 不为空的时候为下一节点
 */
public class Q160IntersectionOfTwoLinkedLists {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode listNode6 = new ListNode(6);
        listNode6.next = listNode3;
        ListNode intersectionNode = getIntersectionNode(listNode1, listNode6);
        System.out.println("intersectionNode = " + intersectionNode.val);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            if (p1 == null) {
                p1 = headB;
            } else {
                p1 = p1.next;
            }
            if (p2 == null) {
                p2 = headA;
            } else {
                p2 = p2.next;
            }
        }
        return p1;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
